package com.dwliu.sort;

public class MergeSort {

	/**
	 * 合并排序，利用分而治之的思想，两个已经排序好的序列合并成一个排序好的序列
	 * 写算法时，merge+sort
	 * @param a
	 */
	public static void mergeSort(int a[]){
		sort(a, 0 ,a.length-1);
	}
	
	/**
	 * 将一个序列进行合并排序
	 * @param a
	 * @param left
	 * @param right
	 */
	private static void sort(int a[],int left, int right){
		int middle = (left+right)/2;
		if(left<right){
			sort(a, left, middle);
			sort(a, middle+1, right);
			merge(a, left, middle, right);
		}
	}
	
	private static void merge(int a[], int left, int mid, int right){
		int [] b =new int [right-left+1];
		int i = left, j = mid+1, index=0;
		while(i<=mid && j<=right){
			if(a[i]<=a[j]){
				b[index] = a[i];
				i++;
			}else{
				b[index] = a[j];
				j++;
			}
			index++;
		}
		while(i<=mid){
			b[index] = a[i];
			i++;
			index++;
		}
		while(j<=right){
			b[index] = a[j];
			j++;
			index++;
		}

		System.arraycopy(b, 0, a, left, b.length);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a []= {1,6,3,4,5};
		for(int t: a)
			System.out.print(t+" ");
		System.out.println();
		mergeSort(a);
		for(int t: a)
			System.out.print(t+" ");	
	}

}
